package com.code.sort;

import java.util.Arrays;

public class MergeSort {
    public static void sort(int[] arr,int left,int right,int[] temp){
        if(left < right){
            int center = (left+right)/2;
            sort(arr,left,center,temp);
            sort(arr,center+1,right,temp);
            mergeSort(arr,left,center,right,temp);
        }
    }

    public static void mergeSort(int[] arr, int left, int center, int right, int[] temp){
        int l1 = left;
        int l2 = center+1;
        int i = 0; //临时数组下标
        //有序数组合并
        while(l1 <= center && l2 <= right){
            if(arr[l1] <= arr[l2]){
                temp[i++] = arr[l1++];
            }else{
                temp[i++] = arr[l2++];
            }
        }
        while(l1 <= center){
            temp[i++] = arr[l1++];
        }
        while(l2 <= right ){
            temp[i++] = arr[l2++];
        }
        int iTemp = i;
        i =0;
        while(left < iTemp){
            arr[left++] = temp[i++];
        }
        System.out.println(Arrays.toString(arr));
    }

    public static void main(String[] args) {
        int[] arr = new int[]{4,3,8,5,6};
        int[] temp = new int[arr.length];
        sort(arr,0,arr.length-1,temp);
        System.out.println(Arrays.toString(arr));
    }
}
